public class Solution52 {
    public int totalNQueens(int n) {
        int[] x = new int[n];
        return queens(x, 0);
    }

    private int queens(int[] x, int k) {
        int n = x.length;
        if (k == n) {
            return 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            x[k] = i;
            if (!isValid(x, k)) {
                ans += queens(x, k + 1);
            }
        }

        return ans;
    }

    private boolean isValid(int[] x, int k) {
        for (int i = 0; i < k; i++) {
            if (x[i] == x[k] || Math.abs(x[i] - x[k]) == Math.abs(i - k)) {
                return true;
            }
        }

        return false;
    }
}
